package 剑指offer;

public class _14_2剪绳子2 {
	public static void main(String[] args) {
		System.out.println(cuttingRope(54));
	}
	
	 public static int cuttingRope(int n) {
	    	if(n<=3) return n-1;
	    	int a=n/3,b=n%3,sum=0;
	    	if(b==0) sum=loopMod(a,1);
	    	if(b==1) sum=loopMod(a-1,4);
	    	if(b==2) sum=loopMod(a,2);
	    	return sum;
	    }
	 public static int loopMod(int a,int b) {
		long res=1;
		while(a>0) {
			res=(res*3)%1000000007;
			a-=1;
		}
		return (int) ((res*b)%1000000007);
	}
}
